package Tree;

public class _337_HouseRobberIII {
    int depth = 1;
    int[] levelSum;
    int[] dpSum;
    //wrong answer list:1 odd and even sum;2:use dynamic programming with level sum.
    public int rob_w(TreeNode root) {
        getDepth(root, 1);
        this.levelSum = new int[depth];
        this.dpSum = new int[depth];
        getSum(root, 1);
        if (depth ==1) {
            return levelSum[0];
        } else if (depth == 2) {
            return Math.max(levelSum[0], levelSum[1]);
        } else {
            dpSum[0] = levelSum[0];
            dpSum[1] = levelSum[1]>levelSum[0]?levelSum[1]:levelSum[0];
            for (int i = 2; i < depth; i++) {
                dpSum[i] = levelSum[i] + dpSum[i - 2] > dpSum[i - 1] ? levelSum[i] + dpSum[i - 2] : dpSum[i - 1];
            }
            return dpSum[depth - 1];
        }
    }

    public void getSum(TreeNode root, int level) {
        if (root != null) {
            levelSum[level-1] +=root.val;
            getSum(root.left, level + 1);
            getSum(root.right, level + 1);
        }
    }

    public void getDepth(TreeNode root, int level) {
        if (root != null) {
            if (level > depth) {
                depth = level;
            }
            getDepth(root.left, level + 1);
            getDepth(root.right, level + 1);
        }
    }

    //reference solution 1:use recursion
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int val = 0;
            if (root.left != null) {
                val += rob(root.left.left) + rob(root.left.right);
            }
            if (root.right != null) {
                val += rob(root.right.left) + rob(root.right.right);
            }
            return Math.max(val + root.val, rob(root.left) + rob(root.right));
        }
    }
}
